import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/*
 * @lc app=leetcode.cn id=239 lang=java
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start
// class MyQueue{
//     Deque<Integer> deque=new LinkedList<>();
//     void poll(int val){
//         if(!deque.isEmpty()&&val==deque.peek()){
//             deque.poll();
//         }
//     }

//     void add(int val){
//         while(!deque.isEmpty()&&val>deque.getLast()){
//             deque.pollLast();
//         }
//         deque.add(val);
//     }

//     int peek(){
//         return deque.peek();
//     }
// }
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // if(nums.length==1){
        //     return nums;
        // }
        // int len=nums.length-k+1;
        // //存放结果元素的数组
        // int[] res=new int[len];
        // int num=0;
        // MyQueue myQueue=new MyQueue();
        // for(int i=0;i<k;i++){
        //     myQueue.add(nums[i]);
        // }
        // res[num++]=myQueue.peek();
        // for(int i=k;i<nums.length;i++){
        //     myQueue.poll(nums[i-k]);
        //     myQueue.add(nums[i]);
        //     res[num++]=myQueue.peek();
        // }
        // return res;
        if(nums.length==1){
            return nums;
        }
        int len=nums.length-k+1;
        int num=0;
        //存放结果
        int[] res=new int[len];
        Deque<Integer> queue=new ArrayDeque<>();
        for(int i=0;i<nums.length;i++){//要求最大值，保证单调递减队列
           //队尾去除不满足单调性的元素
           while(!queue.isEmpty()&&nums[i]>nums[queue.peekLast()]){
                queue.pollLast();
           }
           //队头确定是否满足范围，若不满足则确定新的队头（所求极大值）
           while(!queue.isEmpty()&&queue.peek()<i-k+1){
                queue.poll();
           }
           queue.offer(i);
           //取极值
           if(i>=k-1){
               res[num++]=nums[queue.peek()];
           }
        }
        return res;
    }
}
// @lc code=end

